package problem213_House_Robber_II;

/**
 * There are two cases here 
 * 1) 1st element is included and last is not included 
 * 2) 1st is not included and last is included.
 * Therefore, we can use the similar dynamic 
 * programming approach to scan the array twice and get the larger value.
 * @author I321035
 *
 */
public class Solution {
	public int rob(int[] nums){
		if(nums==null || nums.length==0)
	        return 0; 
		if(nums.length==1)
			return nums[0];
		return Math.max(helper(nums,1,nums.length-1), helper(nums,0,nums.length-2));
	}
	
	private int helper(int[] nums,int start,int end){
		if(start==end)
			return nums[start];
		int[] dp=new int[nums.length];
		dp[start]=nums[start];
		dp[start+1]=Math.max(nums[start], nums[start+1]);
		for(int i=start+2;i<=end;i++){
			dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);
		}
		return dp[end];
	}
}
